Національний Університет “Києво-Могилянська академія” Департамент Комп’ютерних Технологій Методи стискання інформації: огляд та порівняльний аналіз Курсова робота студента IV р.н. Чаговця Олексія Керівник: доц. Ставровський А.Б. Київ - 1999 Зміст ЗМІСТ 2 ВСТУП. ОГЛЯД МЕТОДІВ СТИСКАННЯ ІНФОРМАЦІЇ. 3 МЕТОДИ КОДУВАННЯ. 5 Кодування Хаффмена. 6 Арифметичне кодування. 8 МОДЕЛІ ВХІДНОГО ПОТОКУ. 10 Стискання за допомогою купки книжок 11 ДВОРІВНЕВЕ КОДУВАННЯ. АЛГОРИТМ ЛЕМПЕЛЯ-ЗІВА. 12 СІМЕЙСТВО АЛГОРИТМІВ LZ78 (LZW, MW, AP, Y) 14 ВИСНОВКИ. 17 СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ. 18 Вступ. Огляд методів стискання інформації. Методи стискання інформації мають досить довгу історію. В цьому розділі спробуємо навести короткий огляд основних ідей та їх реалізацій. Існує низка “наївних” підходів до цієї проблеми. Найбільш відомий – це кодування довжин серій (run length encoding, RLE). Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” (наприклад, формат PCX використовує кодування RLE). Недоліки методу RLE є очевидними: це, передусім, низька пристосованість до багатьох розповсюджених типів файлів, наприклад, текстових: у загальному випадку реально стиснути можна лише ланцюжки проміжків на початку абзаців. Саме тому цей метод можна ефективно використовувати лише у комбінації з вторинним кодуванням. Цей підхід реалізовано в алгоритмі кодування факсів: спочатку зображення розбивається на чорні та білі крапки, що перетворюються алгоритмом RLE на потік довжин серій, а потім ці довжини серій кодуються за методом Хаффмена зі спеціально підібраним деревом. Тут зробимо невеличкий відступ для уточнення термінології. Надалі будемо розглядати компресор (compressor) як програму, що перетворює масив символів деякого алфавіту в інший, бажано меншого за розміром. Часто роль цього масиву виконує безструктурний двійковий файл (подібний до файла MS-DOS або UNIX), а роль масиву символів вхідного алфавіту – 256 можливих значень байта (але не завжди). Відповідно, декомпресор (decompressor) – програма, що виконує зворотнє перетворення, до того ж виконує його однозначно. Таким чином, ми виключаємо з розгляду методи стискання, що втрачають інформацію (наприклад, метод стискання зображень JPEG, що базується на перетворенні кольорів, які практично неможливо розрізнити людським оком). При цьому найбільш цікавими є однопрохідні алгоритми, що стискають не просто файл прямого доступу, а потік – файл, що не дозволяє позиціонування та скролінгу (подібно до програмного каналу (pipe) в UNIX). Такі алгоритми мають більш широку сферу застосувань, зокрема вони зручніші для апаратної реалізації в складі інтелектуальних контролерів пристроїв. Наприклад, протокол v42bis, що застосовується в модемах – це реалізація модифікації алгоритму LZW. Фундаментальне поняття теорії інформації – ентропія, яку можна розглядати як міру кількості інформації в повідомленні. Під вартістю мається на увазі середня довжина кодового слова (в бітах) на один символ вихідного тексту. Надлишковість кодування дорівнює різниці між вартістю кодування та ентропією вихідного повідомлення з розрахунку на один символ. Надлишковість також можна розглядати як відношення кількості надлишкових символів до кількості корисних: за таких визначень очевидно, що надлишковість завжди є невід’ємною. Ефективний алгоритм стискання має мінімізувати надлишковість (в ідеальному випадку – звести до нуля). Фундаментальна теорема Шеннона про кодування джерел стверджує, що вартість кодування завжди не менша, ніж ентропія джерела, хоча й може бути як завгодно близька до неї. Це твердження встановлює теоретичні границі стискання даних. Далі, процес...